package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Sout;
import com.wtgroup.demo.common.util.Tools;
import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

import java.util.Arrays;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/9 10:35
 */
public class Q_背包问题 {
    /*
    物品
    values: [10,5,6,...]
    weights: [2,4,50,...]
    背包容量 100
    怎么装物品, 最后的价值和最大?
    */

    public static void main(String[] args) {
        Judger.of(() -> {
            int[] values = RandomUtil.randomArray(RandomUtil.randomInt(100, 101), 0, 1000);
            int[] weights = RandomUtil.randomArray(values.length, 1, 1000);
            int bag = RandomUtil.randomInt(0, 1000);
            Sout.println(
                    Tools.time(() -> {
                        int r1 = D.func(values, weights, bag);
                    }),
                    Tools.time(() -> {
                        int r2 = S.maxValue(weights, values, bag);
                    })
            );
            return  true;
        }).setIterCount(100).start().print();
    }

    private static void test1() {
        Judger.of(() -> {
            int[] values = RandomUtil.randomArray(RandomUtil.randomInt(0, 10), 0, 10);
            int[] weights = RandomUtil.randomArray(values.length, 1, 10);
            // int[] values = new int[]{7, 5, 6, 1};
            // int[] weights = new int[]{6, 7, 5, 6};
            int bag = 5;
            // int r1 = S_暴力递归.func(values, weights, bag);
            int r1 = D.func(values, weights, bag);
            // int r2 = S_贪心.func(values, weights, bag);
            int r2 = S.maxValue(weights, values, bag);
            if (r1 != r2) {
                Sout.println(values);
                Sout.println(weights);
                Sout.println("r1: ", r1, ", r2: ", r2);
            }
            return r1 == r2;
        }).setIterCount(100).start().print();
    }

    static class S_暴力递归 {

        static int func(int[] values, int[] weights, int bag) {
            return func0(values, weights, bag, 0, bag);
        }

        static int func0_1(int[] values, int[] weights, int bag, int i, int valueResult, int weightResult) {
            if (weightResult >= bag || i >= values.length) {
                return valueResult;
            }
            // 放
            int r1 = 0;
            if (weightResult + weights[i] <= bag) {
                r1 = func0_1(values, weights, bag, i + 1, valueResult + values[i], weightResult + weights[i]);
            }
            // 不放
            int r2 = func0_1(values, weights, bag, i + 1, valueResult, weightResult);

            return Math.max(r1, r2);
        }

        static int func0(int[] values, int[] weights, int bag, int i, int rest) {
            if (rest <= 0 || i >= values.length) {
                return 0;
            }
            // 放
            int r1 = 0;
            if (weights[i] <= rest) {
                r1 = values[i] + func0(values, weights, bag, i + 1, rest - weights[i]);
            }
            // 不放
            int r2 = func0(values, weights, bag, i + 1, rest);

            return Math.max(r1, r2);
        }

    }

    static class S {
        // 所有的货，重量和价值，都在w和v数组里
        // 为了方便，其中没有负数
        // bag背包容量，不能超过这个载重
        // 返回：不超重的情况下，能够得到的最大价值
        public static int maxValue(int[] w, int[] v, int bag) {
            if (w == null || v == null || w.length != v.length || w.length == 0) {
                return 0;
            }
            // 尝试函数！
            return process(w, v, 0, bag);
        }

        // index 0~N
        // rest 负~bag
        public static int process(int[] w, int[] v, int index, int rest) {
            if (rest < 0) {
                return -1;
            }
            if (index == w.length) {
                return 0;
            }
            int p1 = process(w, v, index + 1, rest);
            int p2 = 0;
            int next = process(w, v, index + 1, rest - w[index]);
            if (next != -1) {
                p2 = v[index] + next;
            }
            return Math.max(p1, p2);
        }
    }

    static class D {
        static int func(int[] values, int[] weights, int bag) {
            int N = values.length;
            int[][] dp = new int[N + 1][bag + 1];

            for (int i = N - 1; i >= 0; i--) {
                for (int rest = bag; rest > 0; rest--) {
                    int r1 = 0;
                    if (weights[i] <= rest) {
                        r1 = values[i] + dp[i + 1][rest - weights[i]];
                    }
                    int r2 = dp[i + 1][rest];
                    dp[i][rest] = Math.max(r1, r2);
                }
            }

            // return func0(values, weights, bag, 0, bag, dp);
            return dp[0][bag];
        }


    }


    // 贪心是失效的
    static class S_贪心 {
        static int func(int[] values, int[] weights, int bag) {
            Item[] items = new Item[values.length];
            for (int i = 0; i < values.length; i++) {
                int value = values[i];
                items[i] = new Item(value, weights[i]);
            }
            Arrays.sort(items);
            int wgtres = 0;
            int valueres = 0;
            for (Item item : items) {
                if (wgtres + item.weight > bag) {
                    break;
                }
                valueres += item.value;
            }

            return valueres;
        }
    }

    @NoArgsConstructor
    @AllArgsConstructor
    static class Item implements Comparable<Item> {
        int value;
        int weight;
        double order;

        public Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
            this.order = weight / value;
        }

        @Override
        public int compareTo(Item o) {
            return this.order < o.order ? -1 : (this.order == o.order ? 0 : 1);
        }
    }

}
